package exercises.leetcode;

import exercises.newcoder.util.ListNode;

/**
 * <a href="https://leetcode-cn.com/problems/merge-two-sorted-lists/">
 * 21. 合并两个有序链表</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * <p>
 * 示例 1：
 * <p>
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * <p>
 * 示例 2：
 * <p>
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * <p>
 * 示例 3：
 * <p>
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 *  
 * <p>
 * 提示：
 * <li>两个链表的节点数目范围是 [0, 50]</li>
 * <li>-100 <= Node.val <= 100</li>
 * <li>l1 和 l2 均按 非递减顺序 排列</li>
 *
 * @author or2
 * @date 2021年09月28日 时间: 11:23
 */
public class No21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0, l1);
        l1 = head;
        for (ListNode l2Next = l2; l2 != null; l2 = l2Next) {
            /*l2结点 > l1最大值*/
            if (l1.next == null) {
                l1.next = l2;
                return head.next;
            }
            /*根据结点大小不断插入*/
            if (l2.val >= l1.next.val)
                l1 = l1.next;
            else {
                l2Next = l2.next;
                l2.next = l1.next;
                l1.next = l2;
                l1 = l2;
            }
        }

        return head.next;
    }
}
